package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class IntersectionOfTwoLinkedLists {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {


        // 解法一  ： 哈希表
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            Set<ListNode> valSet = new HashSet<ListNode>();

            ListNode temp = headA;
            while (temp != null) {
                valSet.add(temp);
                temp = temp.next;
            }
            temp = headB;
            while (temp != null) {
                if (valSet.contains(temp)) {

                    return temp;
                }
                temp = temp.next;
            }
            return null;
        }



        // 解法二  ： 双指针

        //  https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/1/intersection-of-two-linked-lists-shuang-zhi-zhen-l/?envType=problem-list-v2&envId=2cktkvj&difficulty=EASY


        //

        //
        public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
             if(headA==null||headB==null){
                 return null;
             }
            ListNode pA = headA;
            ListNode pB = headB;
            while (pA != pB) {
                pA= pA==null?headB:pA.next;
                pB= pB==null?headA:pB.next;
            }

            return pA;


        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new IntersectionOfTwoLinkedLists().new Solution();
        // put your test code here



        ListNode headA = ListNode.createHead(new int[]{1,9,1,2,4});
        ListNode headB = ListNode.createHead(new int[]{3,2,4});
        solution.getIntersectionNode2(headA, headB);


    }
}
